package EstructurasDeDatos;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


public class ArbolConCiclo extends Arbol{

	private int numeracion;
	private int bajo;
	private List<ArbolConCiclo> hijosRetorno;
	
	public ArbolConCiclo(String raiz) {
		super(raiz);
		hijosRetorno=new ArrayList<ArbolConCiclo>();	
	}
	
	public ArbolConCiclo(String raiz,List<Arbol> sons,List<ArbolConCiclo> ret){
		super(raiz);
		hijos=sons;
		hijosRetorno=ret;
		id=raiz;
	}
	
	public void agregarHijo(ArbolConCiclo a){
		//TODO verificar q el arbol no exista ya
		hijos.add(a);
	}
	
	public void agregarHijoRetorno(ArbolConCiclo a){
		//TODO verificar q el arbol no exista ya
		hijosRetorno.add(a);
	}
	
	public void agregarHijos(List<Arbol> sons){
		//TODO verificar que no exista ya alguno de los hijos
		hijos.addAll(sons);
	}
	
	public void agregarHijosRetorno(List<ArbolConCiclo> sons){
		//TODO verificar que no exista ya alguno de los hijos
		hijosRetorno.addAll(sons);
	}
	
	public List<ArbolConCiclo> getHijosRetorno(){
		return hijosRetorno;
	}
	
	public void setNumeracion(int val){
		numeracion=val;
	}
	
	public int getNumeracion(){
		return numeracion;
	}
	
	public void setBajo(int val){
		bajo=val;
	}
	
	public int getBajo(){
		return bajo;
	}
	
	public int numerarNodos(int valorInicial){
		numeracion=valorInicial;
		if(!hijos.isEmpty())
			for(Arbol a : hijos){
				valorInicial=((ArbolConCiclo)a).numerarNodos(++valorInicial);
			}
		return valorInicial;
	}
	
	public void calcularBajo(){
		//Calculo el bajo de este nodo
		Deque<ArbolConCiclo> porVisitar=new ArrayDeque<ArbolConCiclo>();
		porVisitar.addFirst(this);
		int minVal=getNumeracion();
		while(!porVisitar.isEmpty()){
			ArbolConCiclo nodoActual=porVisitar.removeFirst();
			if(nodoActual.getNumeracion()<minVal)
				minVal=nodoActual.getNumeracion();
			List<ArbolConCiclo> hijitos=nodoActual.getHijosRetorno();
			if(!hijitos.isEmpty()){
				for(ArbolConCiclo a : hijitos){
					if(a.getNumeracion()<minVal)
						minVal=a.getNumeracion();
				}
			}
			else{
				List<Arbol> hijosDir=nodoActual.getHijos();
				if(!hijosDir.isEmpty()){
					for(Arbol a : hijosDir)
						porVisitar.addFirst((ArbolConCiclo)a);
				}
			}
		}
		bajo=minVal;

		//Debo decirle a cada uno de mis hijos que calcule su bajo
		for(Arbol a : hijos)
			((ArbolConCiclo) a).calcularBajo();
	}
	
	public List<String> obtenerArticulaciones(){
		Deque<Arbol> porVisitar=new ArrayDeque<Arbol>();
		List<String> articulaciones=new ArrayList<String>();
		
		//Analizamos la raiz
		if(this.getHijos().size()>1)
			articulaciones.add(this.getId());
		for(Arbol arb : this.getHijos())
			porVisitar.addFirst(arb);
		
		//Analizamos el resto de los nodos
		while(!porVisitar.isEmpty()){
			Arbol actual=porVisitar.removeFirst();
			List<Arbol> hijitos=actual.getHijos();
			for(Arbol a : hijitos){
				if(((ArbolConCiclo)a).getBajo()>=((ArbolConCiclo)actual).getNumeracion()){
					articulaciones.add(actual.getId());
					break;
				}
			}
			porVisitar.addAll(hijitos);
		}
		return articulaciones;
	}
	
}
